package lc20240704;
/**
  * @description 解密数字
  * @author 不知名帅哥
  * @date 2024/7/4 9:22
  * @version 1.0
*/
public class DecodeWays {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int n = s.length();
        int[] dp = new int[n + 1];
        
        dp[0] = 1; // 空字符串有一种解码方式
        dp[1] = s.charAt(0) != '0' ? 1 : 0; // 单个字符为0时没有解码方式
        
        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            
            // 如果当前字符可以解码（即1-9之间），则继承前一个字符的解码方式数
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i - 1];
            }
            
            // 如果当前和前一个字符可以解码成一个字母（即10-25之间），则继承前两个字符的解码方式数
            if (twoDigits >= 10 && twoDigits <= 25) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }

    public static void main(String[] args) {
        DecodeWays solution = new DecodeWays();
        String ciphertext = "226";
        int result = solution.numDecodings(ciphertext);
        System.out.println("Number of ways to decode: " + result); // 输出 3
    }
}
